1. Field of the Invention
The present invention relates to pseudo-random number generators and, in particular to pseudo-random number generators suitable for key generators in bus encryption.
2. Description of Related Art
A well-known random number generator is illustrated in FIG. 12. The pseudo-random number generator of FIG. 12, which is also referred to as a linear feedback shift register, includes a plurality of memory elements 51, 52, 53, 54 which, in FIG. 12, are numbered from 0 to n. The memory cells can be initialized to a starting value via initializing means 55. The memory cells 51-54, taken together, form feed forward means, whereas the linear shift register formed by the memory cells 51-54 is fed back via feedback means coupled between an output 56 of the circuit and the memory cell n. The feedback means in particular includes one or several combining means 57, 58 fed by respective feedback branches 59a, 59b, 59c, as is exemplarily illustrated in FIG. 12. The output value of the last combining means 58 is fed to the memory cell n which, in FIG. 12, is referred to by 54.
The linear feedback shift register illustrated in FIG. 12 is operated by a clock such that in each clock cycle the occupancy of the memory cells is shifted by one step, referring to FIG. 12, to the left so that in each clock cycle the state stored in the memory means 51 can be output as a number, wherein at the same time the value at the output of the last combining means 58 is fed into the first memory unit n of the sequence of memory units. The linear feedback shift register illustrated in FIG. 12 thus provides a sequence of numbers responsive to a sequence of clock cycles. The sequence of number obtained at the output 56 depends on the starting state produced by the initializing means 55 before taking the shift register into operation. The starting value input by the initializing means 55 is also referred to as a seed, which is why such arrangements as illustrated in FIG. 12 are also referred to as seed generators.
The sequence of numbers obtained at the output 56 is called a pseudo-random sequence of numbers since the numbers apparently follow one another in a random manner, but, altogether, are periodical even if the period duration is great. Additionally, the sequence of numbers can be repeated uniquely and thus has a pseudo-random nature when the initializing value fed to the memory elements by the initializing means 55 is known. Such shift registers are, for example, employed as key stream generators to provide a stream of encryption/decryption keys depending on a special initializing value (seed).
Such shift registers illustrated in FIG. 12 have the disadvantage of a low linear complexity. With an n-bit LFSR (LFSR=linear feedback shift register), for example, 2 n bits of the output sequence are sufficient to calculate the entire sequence. The advantage of such LFSRs illustrated in FIG. 12, however, is that the hardware complexity is very low. Additionally, there are irregularly clocked LFSRs. They are of a somewhat increased hardware complexity with a mostly smaller period. The linear complexity, however, may be increased considerably. A disadvantage of such irregularly clocked devices, however, is the fact that, due to the irregular clocking, the output sequence may be derived in principle by measuring the current using an SPA (SPA=simple power analysis). By using the shift register devices as parts of key generators which produce data to be kept secret inherently, i.e. key data, it is of particular importance for them to be safe from any kinds of cryptographic attacks.
On the other hand, there is, however, the requirement in such devices, in particular when they are accommodated on chip cards, that the hardware complexity be small. Put differently, the chip area that devices of this kind occupy must be as small as possible. This is due to the fact that, in semiconductor manufacturing, the chip area of an entire device in the end determines the price and thus the profit margin of the chip producer. In addition, a specification, in particular in chip cards, for example, is for a customer to determine a maximum area in square millimeters a processor chip may comprise, on which functionalities of the most different kinds must be accommodated. Thus, it is the task of the circuit producer to distribute this precious area to the individual components. With regard to cryptographic algorithms, which are getting increasingly complex, chip manufacturers make efforts for the chip to have as much storage capacity as possible to be able to calculate algorithms requiring lots of working memory within a reasonable time. The chip area for key generators and other components of this kind thus has to be kept as small as possible in order to be able to accommodate a greater storage capacity on the chip area given.
The general requirement for key generators or devices for generating a pseudo-random sequence of numbers thus is to be safe on the one hand and, on the other hand, to require the smallest amount of space possible, i.e. to entail the smallest hardware complexity possible.
Random number generators can, for example, be employed for bus encryption. Here, reference is made to FIG. 13 showing a conventional bus encryption concept. At the beginning of a bus, a bit mi to be transferred via the bus must be encrypted for protection while being transmitted on the bus line. At the end of the bus, the encrypted bit must be converted again to the unencrypted bit in order for the bit mi to be processed further. The beginning of the bus can, for example, be the output of a processor, whereas the end of the bus may be the input into a memory in which the bit is typically re-encrypted to a “harder” type of encryption to be finally stored in the memory. Alternatively, the beginning of the bus may also be a memory output interface and the end of the bus may be an input of a processor.
In general, it is assumed that bits transmitted on bus lines are in particular danger there so that bus encryption is employed here. An XOR gate including a message bit mi to be encrypted at its first input and including a key bit ki at its second input, which is typically generated by a random number generator, is used as typical encryption means. Typically, the temporal sequence of key bits ki, i being the time index, is a pseudo-random number sequence, i.e. a sequence of numbers looking like a random number sequence which, however, is deterministic in that it can be reproduced. Typical random number generators are, as will be explained later, feedback shift registers producing, departing from a defined starting state (seed), a defined output sequence having a certain period duration.
In bus encryption, as is shown in FIG. 13, the same key sequence generator, having an identical setup, is used at the beginning and the end of the bus, wherein the key sequence generators—except for a delay, which can often be neglected, which the encrypted bit ci “suffers” due to the transfer via a bus of a certain length—operate synchronously.
Up to now, a key sequence generator has been used as the shift register. Since a bus is made up of several bus lines, such as, for example, of 32 bus lines, each bus line is to be provided with a key sequence. This problem can be solved by providing a memory cell in a feedback shift register for each bus line and feeding the state of each memory cell—over the time considered—to the encryption input of bus encryption means/bus decryption means. This means that, for example, the state of the seventh memory cell, over time, serves as the key sequence for encrypting the eighth bus line, that, for example, the state of the sixth memory cell, over time, serves as the key sequence for encrypting the seventh bus line, etc.
Every cell of the shift register will thus be output, wherein this output sequence will then be used for encrypting a corresponding bus line.
This, however, means that the same key sequence is basically always used for encrypting all the bus lines, since the individual key sequences are only shifted versions of one and the same shift register sequence.
From the point of view of safety, this is, of course, of disadvantage in that the attacker, once he has established a key sequence, will automatically obtain all the other key sequences with which the other bus lines are encrypted with this single key sequence by temporal shifting.
Another disadvantage is that shift registers comprising at least as many cells are required as there are bus lines to be supplied. Consequently, a shift register having at least 32 shift register cells is required for a 32-bit wide bus.
In summary, the concept described is of disadvantage in that the safety of the encryption is critical because all the bus lines are encrypted by the same sequence—only temporally shifted—and in that additionally there is an efficiency problem with regard to the chip area consumption, since at least as many memory cells are required as there are bus lines.
In particular with regard to the chip area consumption, it is to be mentioned that this is a considerable cost factor for products offered in large numbers.
Apart from the cost factor, there are further restrictive requirements to the chip area consumption, in particular for chip card applications, since the size of a chip is predetermined by the user, i.e. the chip card manufacturer. Typically, the chip card manufacturer has the possibility to divide the chip area available according to his demands for logic elements, memory elements, etc. Due to high computing performance, the highest possible portion is thus required for working memory and computing power so that area savings with every single element, such as, for example, a shift register pseudo-random number generator, are of great importance to meet the overall chip area criteria.